"""170"""
"""
设计一个接收整数流的数据结构，该数据结构支持检查是否存在两数之和等于特定值。

实现 TwoSum 类：

TwoSum() 使用空数组初始化 TwoSum 对象
void add(int number) 向数据结构添加一个数 number
boolean find(int value) 寻找数据结构中是否存在一对整数，使得两数之和与给定的值相等。如果存在，返回 true ；否则，返回 false 。
"""
"""
示例：

输入：
    ["TwoSum", "add", "add", "add", "find", "find"]
    [[], [1], [3], [5], [4], [7]]
输出：
    [null, null, null, null, true, false]

解释：
    TwoSum twoSum = new TwoSum();
    twoSum.add(1);   // [] --> [1]
    twoSum.add(3);   // [1] --> [1,3]
    twoSum.add(5);   // [1,3] --> [1,3,5]
    twoSum.find(4);  // 1 + 3 = 4，返回 true
    twoSum.find(7);  // 没有两个整数加起来等于 7 ，返回 false
 

提示：
    -105 <= number <= 105
    -231 <= value <= 231 - 1
    最多调用 104 次 add 和 find
"""


class TwoSum:

    def __init__(self):
        self.li = []
        self.is_sort = False

    def add(self, number: int) -> None:
        self.li.append(number)
        self.is_sort = False

    def find(self, value: int) -> bool:
        if not self.is_sort:
            self.li.sort()
            self.is_sort = True
        left, right = 0, len(self.li) - 1
        while left < right:
            res = self.li[left] + self.li[right]
            if res > value:
                right -= 1
            elif res < value:
                left += 1
            else:
                return True
        return False


class TwoSum_v2:

    def __init__(self):
        self.hashmap = dict()

    def add(self, number: int) -> None:
        self.hashmap[number] = self.hashmap.get(number, 0) + 1

    def find(self, value: int) -> bool:
        for i in self.hashmap:
            cur = value - i
            if cur != i:
                if self.hashmap.get(cur, 0) > 0:
                    return True
            else:
                if self.hashmap[i] > 1:
                    return True
        return False


def test1():
    obj = TwoSum()
    obj.add(1)
    obj.add(3)
    obj.add(5)
    print(obj.find(4))
    print(obj.find(7))


def test2():
    obj = TwoSum()
    obj.add(1)
    obj.add(-1)
    print(obj.find(0))


def test3():
    obj = TwoSum()
    obj.add(1)
    obj.add(1)
    print(obj.find(0))
    print(obj.find(1))
    print(obj.find(2))
    obj.add(-1)
    print(obj.find(0))
    print(obj.find(1))
    print(obj.find(-2))
    obj.add(-1)
    print(obj.find(-2))


if __name__ == '__main__':
    test1()
    # test2()
